import java.util.*;

public class Example {
    public static void main(String args[]) {
        int m, n = 1;
        Scanner in = new Scanner(System.in);
        System.out.print("Enter a positive integer: ");
        m = in.nextInt();
        if (isPrime(m)) n = m;
        else {
            ArrayList<Integer> factors = new ArrayList<>();
            ArrayList<Integer> checked = new ArrayList<>();
            int remainder = m;
            while (!isPrime(remainder)) {
                for (int i = 2; i <= remainder / 2; i++) {
                    if (!isPrime(i)) continue;
                    if (remainder % i == 0) {
                        factors.add(i);
                        remainder /= i;
                        break;
                    }
                }
            }
            factors.add(remainder);
            for (Integer i : factors) {
                if (checked.contains(i)) continue;
                checked.add(i);
                int count = 0;
                for (Integer j : factors)
                    if (i == j) count++;
                if (count % 2 != 0) n *= i;
            }
        }
        System.out.println("The smallest number n for m * n to be a perfect square is " + n);
        System.out.println("m * n = " + (m * n));
    }

    public static boolean isPrime(int x) {
        if (x <= 1) return false;
        if (x == 2) return true;
        if (x % 2 == 0) return false;
        for (int i = 3; i <= Math.sqrt(x + 1); i += 2) {
            if (x % i == 0) return false;
        }
        return true;
    }
}